Dynamic Programming

Friday, June 26, 2015

9:37 AM

<<dynamic-programming.pdf>>

Inserted from: <file://\\psf\Dropbox\Schoolworks\Waterloo Terms\4B\CS431 Algo\dynamic-programming.pdf>

Machine generated alternative text: •-a.—-r.—_ Cam
Coin Changing
Problem
Coin Changing
Instance: A ¡Est of coin denominations. 1 = .4. and a
pzsitive ¡nte jet T, which is called the target sum.
Find: An n-tuple of non-negative integers, say.4 = ,..-, a,. such
that T = ED-: a,d, an. such that ‘ = a is minimized.
Let Nì.t] denote the optimal solution to the subproblem consisting of the
fir. i coin denominations D:. . .p and :aget sum t. Le: A.t denote
te n_mber of coins o cenomva:ion d _sed n the optimal solution to
this subp’oblem.
.7 S- Was, 5 UI? 22?
•a’_z___ Cam cta,$qg
A Dynamic Programming Algorithm for Coin
Changing
Algorithm: Coin Changing(da... - ¿n. T)
comment: d. = 1
for t , 0 to T
1_,v.1.t] — t
do <14•i:t t
for — 2 to n
(for t — C’ to T
—
I4:i.t:—0
do d forj—lto
fj--Xi—1.t—jdJcX’z.tJ
: I do then
j t t
return
S «s. - WflitS., 5Z2 225 .127

$Machine generated alternative text: Lsga Can.,.. S.ajn.. Longest Common Subsequence Problem Longest Common Subsequence Instance: Treo sequences X = (‘i,... z) and Y = .. , y,j over some finite alpha bet r. Find: A maximum length sequence Z that is a subseavence of bath X and Y. Z = (21,.... 2k) is a subsequence of X if the’e exit indices 1 i <...< ixm such thatt =z,. 1 i ¿ Similarty. Z is a subsequer,ce of Y [f there exist (possibly different) ndces 1 < h1 < ..- chj (n such that zj = ys. 1 J L ! S .J WbItte’, mii iii ‘ iii .3Jl_t.S Lga Cann. sase.... fl Computing the Length of the LCS of X and Y Algorithm: LCSI(X = (r: x,,LY = fyj,... for t — 0 to ni do cì.0 — for j - D to n do c:o,j: o for t 1 to ni (for j — 1 to n do ) 1’i do thenc{i,j.s—ci—1.j—1]+1 ( L else c:t,j: m&’c-ci.j — — return (c[m. n::,: S flh.ts, 5ZS in ‘UT$

$Machine generated alternative text: •3a_.P_fl L_ga Can.... S.S.... Finding the LCS of X and Y Algorithm: LCS2(X = (x ,...,x,j.Y = for t.— O to ni do ci,O] .— 0 for j —0 to n do c[o,j: o for t — 1 to ni (for j — 1 to then do d else if ci.j—ij > c:t— 1d then {ciM —ci,j—f Ici. ( — cl — 1.j I. 1ee w:;:—a return (c. r); ! • —‘——:&i ! tintas. 20L! ::3 ir Lela Ca,.,,.r Staa’z. Finding the LCS Algorithm: F1ndLCS(c, r, t) — () i—ni j—n while mizi{i.j} > 0 (if ir[t.j] =UL I (seq—zn seQ then ¿t—t—l do I. . . ti) - lelse if rï,f =L thenj—j—1 lelse 1— t—1 return (seq) taitas, 5ZS 124 .‘ 12?$

Machine generated alternative text: Mnevsn L.g flia.a
Minimum Length Triangulation
Problem
Minimum Length Triangulation vi
Instance: n points ql.. . . ,q, in the EucL’dean pane that ibm, a convex
n-jon P.
Find: A triangu/a non ofF sL’ch that the sum L of the engths of the
n — 2 chords is minimized.
Problem
Minimum Length Triangulation v2
Instance: n points ql.. . . ,q in the Euclidean plane that fon,, a convex
n-jon P.
Find: A trianguiation of P sæsc’ that the sum S. of the perimeters of the
n —3 triangles is minimized.
Let L denote the perimeter of P. Then we have that S, = L + 2S.
Hence the two versions have the me optimal solutions.
4 —s: t#Wtt., U US UT
Mfl.na t.ge TWiaj.Jsbeø
Problem Decomposition
We corsjde version 2 of the proolem
The edge ,q1 is in a triargle with a third vertex q. where
For a given k. ve have:
O the tnangle
O t-e oolygon with vertices q.
O the polygon with vertices q, . q,.
The optimal soLtion will consist of optimal solut[os to the
subproblems in 2 ano 3. along with the triangle in 1.
r ni.ts, az, ¡25 U?

$Machine generated alternative text: .3_7__ Mn.n,n L.go 1Ww.baa Recurrence Relation For 1 1 <j n. le: s:i,j: denote the ootimal solution to the suopeoblem conssting of the polygon having vertices q, qj. Let ak q) denote the perimeter of the triangle having vertices q. The we have the recurrence relat on = min{.Xîq,q,q ‚ — SÌ.Ï — : < k <f) The base cases are given by S[i,i+1 =0 for all t. We compute all s,ç th j—j =. f = tgnta.,. itli ir$